import java.util.Comparator;
import java.util.PriorityQueue;

class Person implements Comparable<Person>{
    public String name;
    public int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }

    @Override
    public int compareTo(Person o) {
        return this.age - o.age;
    }
}
class NameComparator implements Comparator<Person> {

    @Override
    public int compare(Person o1, Person o2) {
        return o1.name.compareTo(o2.name);
    }
}

class Imp implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
}

public class Test2 {

    public static void main(String[] args) {
        int[] array = {1,2,3,4};

    }

    public int[] smallestK(int[] arr, int k) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Imp());
        //O(K)
        for (int i = 0; i < k; i++) {
            maxHeap.offer(arr[i]);
        }
        //O(N-K)*logK

        //k+((N-K)*logK) //k+NlogK-KlogK 约等于 NlogK
        for(int i = k;i < arr.length;i++) {
            int tmp = maxHeap.peek();
            if(arr[i] < tmp) {
                maxHeap.poll();
                maxHeap.offer(arr[i]);
            }
        }

        int[] tmp = new int[k];
        for (int i = 0; i < k; i++) {
            tmp[i] = maxHeap.poll();
        }
        return tmp;

    }

    public int[] smallestK1(int[] arr, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int i = 0; i < arr.length; i++) {
            minHeap.offer(arr[i]);
        }
        int[] tmp = new int[k];
        for (int i = 0; i < k; i++) {
            tmp[i] = minHeap.poll();
        }
        return tmp;
    }





    public static void main3(String[] args) {
        Imp imp = new Imp();
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(imp);
        priorityQueue.offer(10);
        priorityQueue.offer(4);
        System.out.println("====");
    }

    public static void main2(String[] args) {
        Person person1 = new Person("zhangsan",10);
        Person person2 = new Person("lisi",8);
        NameComparator nameComparator = new NameComparator();
        PriorityQueue<Person> priorityQueue = new PriorityQueue<>(nameComparator);
        priorityQueue.offer(person1);
        priorityQueue.offer(person2);
    }

    public static void main1(String[] args) {
        Person person1 = new Person("zhangsan",10);
        Person person2 = new Person("lisi",8);
        System.out.println(person1.compareTo(person2));
        System.out.println(person1.equals(person2));

        NameComparator nameComparator = new NameComparator();
        System.out.println(nameComparator.compare(person1,person2));
    }
}